/*
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

/*
 *
 *
 *
 *
 *
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package java.util.concurrent;

import java.util.AbstractQueue;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.Consumer;

/**
 * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
 * linked nodes.
 *
 * <p>The optional capacity bound constructor argument serves as a
 * way to prevent excessive expansion. The capacity, if unspecified,
 * is equal to {@link Integer#MAX_VALUE}.  Linked nodes are
 * dynamically created upon each insertion unless this would bring the
 * deque above capacity.
 *
 * <p>Most operations run in constant time (ignoring time spent
 * blocking).  Exceptions include {@link #remove(Object) remove},
 * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link
 * #removeLastOccurrence removeLastOccurrence}, {@link #contains
 * contains}, {@link #iterator iterator.remove()}, and the bulk
 * operations, all of which run in linear time.
 *
 * <p>This class and its iterator implement all of the
 * <em>optional</em> methods of the {@link Collection} and {@link
 * Iterator} interfaces.
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @param <E> the type of elements held in this collection
 * @author Doug Lea
 * @since 1.6
 */
public class LinkedBlockingDeque<E>
    extends AbstractQueue<E>
    implements BlockingDeque<E>, java.io.Serializable {

    /*
     * Implemented as a simple doubly-linked list protected by a
     * single lock and using conditions to manage blocking.
     *
     * To implement weakly consistent iterators, it appears we need to
     * keep all Nodes GC-reachable from a predecessor dequeued Node.
     * That would cause two problems:
     * - allow a rogue Iterator to cause unbounded memory retention
     * - cause cross-generational linking of old Nodes to new Nodes if
     *   a Node was tenured while live, which generational GCs have a
     *   hard time dealing with, causing repeated major collections.
     * However, only non-deleted Nodes need to be reachable from
     * dequeued Nodes, and reachability does not necessarily have to
     * be of the kind understood by the GC.  We use the trick of
     * linking a Node that has just been dequeued to itself.  Such a
     * self-link implicitly means to jump to "first" (for next links)
     * or "last" (for prev links).
     */

    /*
     * We have "diamond" multiple interface/abstract class inheritance
     * here, and that introduces ambiguities. Often we want the
     * BlockingDeque javadoc combined with the AbstractQueue
     * implementation, so a lot of method specs are duplicated here.
     */

  private static final long serialVersionUID = -387911632671998426L;

  /**
   * Doubly-linked list node class
   */
  static final class Node<E> {

    /**
     * The item, or null if this node has been removed.
     */
    E item;

    /**
     * One of:
     * - the real predecessor Node
     * - this Node, meaning the predecessor is tail
     * - null, meaning there is no predecessor
     */
    Node<E> prev;

    /**
     * One of:
     * - the real successor Node
     * - this Node, meaning the successor is head
     * - null, meaning there is no successor
     */
    Node<E> next;

    Node(E x) {
      item = x;
    }
  }

  /**
   * Pointer to first node.
   * Invariant: (first == null && last == null) ||
   * (first.prev == null && first.item != null)
   */
  transient Node<E> first;

  /**
   * Pointer to last node.
   * Invariant: (first == null && last == null) ||
   * (last.next == null && last.item != null)
   */
  transient Node<E> last;

  /**
   * Number of items in the deque
   */
  private transient int count;

  /**
   * Maximum number of items in the deque
   */
  private final int capacity;

  /**
   * Main lock guarding all access
   */
  final ReentrantLock lock = new ReentrantLock();

  /**
   * Condition for waiting takes
   */
  private final Condition notEmpty = lock.newCondition();

  /**
   * Condition for waiting puts
   */
  private final Condition notFull = lock.newCondition();

  /**
   * Creates a {@code LinkedBlockingDeque} with a capacity of
   * {@link Integer#MAX_VALUE}.
   */
  public LinkedBlockingDeque() {
    this(Integer.MAX_VALUE);
  }

  /**
   * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity.
   *
   * @param capacity the capacity of this deque
   * @throws IllegalArgumentException if {@code capacity} is less than 1
   */
  public LinkedBlockingDeque(int capacity) {
    if (capacity <= 0) {
      throw new IllegalArgumentException();
    }
    this.capacity = capacity;
  }

  /**
   * Creates a {@code LinkedBlockingDeque} with a capacity of
   * {@link Integer#MAX_VALUE}, initially containing the elements of
   * the given collection, added in traversal order of the
   * collection's iterator.
   *
   * @param c the collection of elements to initially contain
   * @throws NullPointerException if the specified collection or any of its elements are null
   */
  public LinkedBlockingDeque(Collection<? extends E> c) {
    this(Integer.MAX_VALUE);
    final ReentrantLock lock = this.lock;
    lock.lock(); // Never contended, but necessary for visibility
    try {
      for (E e : c) {
        if (e == null) {
          throw new NullPointerException();
        }
        if (!linkLast(new Node<E>(e))) {
          throw new IllegalStateException("Deque full");
        }
      }
    } finally {
      lock.unlock();
    }
  }

  // Basic linking and unlinking operations, called only while holding lock

  /**
   * Links node as first element, or returns false if full.
   */
  private boolean linkFirst(Node<E> node) {
    // assert lock.isHeldByCurrentThread();
    if (count >= capacity) {
      return false;
    }
    Node<E> f = first;
    node.next = f;
    first = node;
    if (last == null) {
      last = node;
    } else {
      f.prev = node;
    }
    ++count;
    notEmpty.signal();
    return true;
  }

  /**
   * Links node as last element, or returns false if full.
   */
  private boolean linkLast(Node<E> node) {
    // assert lock.isHeldByCurrentThread();
    if (count >= capacity) {
      return false;
    }
    Node<E> l = last;
    node.prev = l;
    last = node;
    if (first == null) {
      first = node;
    } else {
      l.next = node;
    }
    ++count;
    notEmpty.signal();
    return true;
  }

  /**
   * Removes and returns first element, or null if empty.
   */
  private E unlinkFirst() {
    // assert lock.isHeldByCurrentThread();
    Node<E> f = first;
    if (f == null) {
      return null;
    }
    Node<E> n = f.next;
    E item = f.item;
    f.item = null;
    f.next = f; // help GC
    first = n;
    if (n == null) {
      last = null;
    } else {
      n.prev = null;
    }
    --count;
    notFull.signal();
    return item;
  }

  /**
   * Removes and returns last element, or null if empty.
   */
  private E unlinkLast() {
    // assert lock.isHeldByCurrentThread();
    Node<E> l = last;
    if (l == null) {
      return null;
    }
    Node<E> p = l.prev;
    E item = l.item;
    l.item = null;
    l.prev = l; // help GC
    last = p;
    if (p == null) {
      first = null;
    } else {
      p.next = null;
    }
    --count;
    notFull.signal();
    return item;
  }

  /**
   * Unlinks x.
   */
  void unlink(Node<E> x) {
    // assert lock.isHeldByCurrentThread();
    Node<E> p = x.prev;
    Node<E> n = x.next;
    if (p == null) {
      unlinkFirst();
    } else if (n == null) {
      unlinkLast();
    } else {
      p.next = n;
      n.prev = p;
      x.item = null;
      // Don't mess with x's links.  They may still be in use by
      // an iterator.
      --count;
      notFull.signal();
    }
  }

  // BlockingDeque methods

  /**
   * @throws IllegalStateException if this deque is full
   * @throws NullPointerException {@inheritDoc}
   */
  public void addFirst(E e) {
    if (!offerFirst(e)) {
      throw new IllegalStateException("Deque full");
    }
  }

  /**
   * @throws IllegalStateException if this deque is full
   * @throws NullPointerException {@inheritDoc}
   */
  public void addLast(E e) {
    if (!offerLast(e)) {
      throw new IllegalStateException("Deque full");
    }
  }

  /**
   * @throws NullPointerException {@inheritDoc}
   */
  public boolean offerFirst(E e) {
    if (e == null) {
      throw new NullPointerException();
    }
    Node<E> node = new Node<E>(e);
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      return linkFirst(node);
    } finally {
      lock.unlock();
    }
  }

  /**
   * @throws NullPointerException {@inheritDoc}
   */
  public boolean offerLast(E e) {
    if (e == null) {
      throw new NullPointerException();
    }
    Node<E> node = new Node<E>(e);
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      return linkLast(node);
    } finally {
      lock.unlock();
    }
  }

  /**
   * @throws NullPointerException {@inheritDoc}
   * @throws InterruptedException {@inheritDoc}
   */
  public void putFirst(E e) throws InterruptedException {
    if (e == null) {
      throw new NullPointerException();
    }
    Node<E> node = new Node<E>(e);
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      while (!linkFirst(node)) {
        notFull.await();
      }
    } finally {
      lock.unlock();
    }
  }

  /**
   * @throws NullPointerException {@inheritDoc}
   * @throws InterruptedException {@inheritDoc}
   */
  public void putLast(E e) throws InterruptedException {
    if (e == null) {
      throw new NullPointerException();
    }
    Node<E> node = new Node<E>(e);
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      while (!linkLast(node)) {
        notFull.await();
      }
    } finally {
      lock.unlock();
    }
  }

  /**
   * @throws NullPointerException {@inheritDoc}
   * @throws InterruptedException {@inheritDoc}
   */
  public boolean offerFirst(E e, long timeout, TimeUnit unit)
      throws InterruptedException {
    if (e == null) {
      throw new NullPointerException();
    }
    Node<E> node = new Node<E>(e);
    long nanos = unit.toNanos(timeout);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
      while (!linkFirst(node)) {
        if (nanos <= 0) {
          return false;
        }
        nanos = notFull.awaitNanos(nanos);
      }
      return true;
    } finally {
      lock.unlock();
    }
  }

  /**
   * @throws NullPointerException {@inheritDoc}
   * @throws InterruptedException {@inheritDoc}
   */
  public boolean offerLast(E e, long timeout, TimeUnit unit)
      throws InterruptedException {
    if (e == null) {
      throw new NullPointerException();
    }
    Node<E> node = new Node<E>(e);
    long nanos = unit.toNanos(timeout);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
      while (!linkLast(node)) {
        if (nanos <= 0) {
          return false;
        }
        nanos = notFull.awaitNanos(nanos);
      }
      return true;
    } finally {
      lock.unlock();
    }
  }

  /**
   * @throws NoSuchElementException {@inheritDoc}
   */
  public E removeFirst() {
    E x = pollFirst();
    if (x == null) {
      throw new NoSuchElementException();
    }
    return x;
  }

  /**
   * @throws NoSuchElementException {@inheritDoc}
   */
  public E removeLast() {
    E x = pollLast();
    if (x == null) {
      throw new NoSuchElementException();
    }
    return x;
  }

  public E pollFirst() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      return unlinkFirst();
    } finally {
      lock.unlock();
    }
  }

  public E pollLast() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      return unlinkLast();
    } finally {
      lock.unlock();
    }
  }

  public E takeFirst() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      E x;
      while ((x = unlinkFirst()) == null) {
        notEmpty.await();
      }
      return x;
    } finally {
      lock.unlock();
    }
  }

  public E takeLast() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      E x;
      while ((x = unlinkLast()) == null) {
        notEmpty.await();
      }
      return x;
    } finally {
      lock.unlock();
    }
  }

  public E pollFirst(long timeout, TimeUnit unit)
      throws InterruptedException {
    long nanos = unit.toNanos(timeout);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
      E x;
      while ((x = unlinkFirst()) == null) {
        if (nanos <= 0) {
          return null;
        }
        nanos = notEmpty.awaitNanos(nanos);
      }
      return x;
    } finally {
      lock.unlock();
    }
  }

  public E pollLast(long timeout, TimeUnit unit)
      throws InterruptedException {
    long nanos = unit.toNanos(timeout);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
      E x;
      while ((x = unlinkLast()) == null) {
        if (nanos <= 0) {
          return null;
        }
        nanos = notEmpty.awaitNanos(nanos);
      }
      return x;
    } finally {
      lock.unlock();
    }
  }

  /**
   * @throws NoSuchElementException {@inheritDoc}
   */
  public E getFirst() {
    E x = peekFirst();
    if (x == null) {
      throw new NoSuchElementException();
    }
    return x;
  }

  /**
   * @throws NoSuchElementException {@inheritDoc}
   */
  public E getLast() {
    E x = peekLast();
    if (x == null) {
      throw new NoSuchElementException();
    }
    return x;
  }

  public E peekFirst() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      return (first == null) ? null : first.item;
    } finally {
      lock.unlock();
    }
  }

  public E peekLast() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      return (last == null) ? null : last.item;
    } finally {
      lock.unlock();
    }
  }

  public boolean removeFirstOccurrence(Object o) {
    if (o == null) {
      return false;
    }
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      for (Node<E> p = first; p != null; p = p.next) {
        if (o.equals(p.item)) {
          unlink(p);
          return true;
        }
      }
      return false;
    } finally {
      lock.unlock();
    }
  }

  public boolean removeLastOccurrence(Object o) {
    if (o == null) {
      return false;
    }
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      for (Node<E> p = last; p != null; p = p.prev) {
        if (o.equals(p.item)) {
          unlink(p);
          return true;
        }
      }
      return false;
    } finally {
      lock.unlock();
    }
  }

  // BlockingQueue methods

  /**
   * Inserts the specified element at the end of this deque unless it would
   * violate capacity restrictions.  When using a capacity-restricted deque,
   * it is generally preferable to use method {@link #offer(Object) offer}.
   *
   * <p>This method is equivalent to {@link #addLast}.
   *
   * @throws IllegalStateException if this deque is full
   * @throws NullPointerException if the specified element is null
   */
  public boolean add(E e) {
    addLast(e);
    return true;
  }

  /**
   * @throws NullPointerException if the specified element is null
   */
  public boolean offer(E e) {
    return offerLast(e);
  }

  /**
   * @throws NullPointerException {@inheritDoc}
   * @throws InterruptedException {@inheritDoc}
   */
  public void put(E e) throws InterruptedException {
    putLast(e);
  }

  /**
   * @throws NullPointerException {@inheritDoc}
   * @throws InterruptedException {@inheritDoc}
   */
  public boolean offer(E e, long timeout, TimeUnit unit)
      throws InterruptedException {
    return offerLast(e, timeout, unit);
  }

  /**
   * Retrieves and removes the head of the queue represented by this deque.
   * This method differs from {@link #poll poll} only in that it throws an
   * exception if this deque is empty.
   *
   * <p>This method is equivalent to {@link #removeFirst() removeFirst}.
   *
   * @return the head of the queue represented by this deque
   * @throws NoSuchElementException if this deque is empty
   */
  public E remove() {
    return removeFirst();
  }

  public E poll() {
    return pollFirst();
  }

  public E take() throws InterruptedException {
    return takeFirst();
  }

  public E poll(long timeout, TimeUnit unit) throws InterruptedException {
    return pollFirst(timeout, unit);
  }

  /**
   * Retrieves, but does not remove, the head of the queue represented by
   * this deque.  This method differs from {@link #peek peek} only in that
   * it throws an exception if this deque is empty.
   *
   * <p>This method is equivalent to {@link #getFirst() getFirst}.
   *
   * @return the head of the queue represented by this deque
   * @throws NoSuchElementException if this deque is empty
   */
  public E element() {
    return getFirst();
  }

  public E peek() {
    return peekFirst();
  }

  /**
   * Returns the number of additional elements that this deque can ideally
   * (in the absence of memory or resource constraints) accept without
   * blocking. This is always equal to the initial capacity of this deque
   * less the current {@code size} of this deque.
   *
   * <p>Note that you <em>cannot</em> always tell if an attempt to insert
   * an element will succeed by inspecting {@code remainingCapacity}
   * because it may be the case that another thread is about to
   * insert or remove an element.
   */
  public int remainingCapacity() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      return capacity - count;
    } finally {
      lock.unlock();
    }
  }

  /**
   * @throws UnsupportedOperationException {@inheritDoc}
   * @throws ClassCastException {@inheritDoc}
   * @throws NullPointerException {@inheritDoc}
   * @throws IllegalArgumentException {@inheritDoc}
   */
  public int drainTo(Collection<? super E> c) {
    return drainTo(c, Integer.MAX_VALUE);
  }

  /**
   * @throws UnsupportedOperationException {@inheritDoc}
   * @throws ClassCastException {@inheritDoc}
   * @throws NullPointerException {@inheritDoc}
   * @throws IllegalArgumentException {@inheritDoc}
   */
  public int drainTo(Collection<? super E> c, int maxElements) {
    if (c == null) {
      throw new NullPointerException();
    }
    if (c == this) {
      throw new IllegalArgumentException();
    }
    if (maxElements <= 0) {
      return 0;
    }
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      int n = Math.min(maxElements, count);
      for (int i = 0; i < n; i++) {
        c.add(first.item);   // In this order, in case add() throws.
        unlinkFirst();
      }
      return n;
    } finally {
      lock.unlock();
    }
  }

  // Stack methods

  /**
   * @throws IllegalStateException if this deque is full
   * @throws NullPointerException {@inheritDoc}
   */
  public void push(E e) {
    addFirst(e);
  }

  /**
   * @throws NoSuchElementException {@inheritDoc}
   */
  public E pop() {
    return removeFirst();
  }

  // Collection methods

  /**
   * Removes the first occurrence of the specified element from this deque.
   * If the deque does not contain the element, it is unchanged.
   * More formally, removes the first element {@code e} such that
   * {@code o.equals(e)} (if such an element exists).
   * Returns {@code true} if this deque contained the specified element
   * (or equivalently, if this deque changed as a result of the call).
   *
   * <p>This method is equivalent to
   * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}.
   *
   * @param o element to be removed from this deque, if present
   * @return {@code true} if this deque changed as a result of the call
   */
  public boolean remove(Object o) {
    return removeFirstOccurrence(o);
  }

  /**
   * Returns the number of elements in this deque.
   *
   * @return the number of elements in this deque
   */
  public int size() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      return count;
    } finally {
      lock.unlock();
    }
  }

  /**
   * Returns {@code true} if this deque contains the specified element.
   * More formally, returns {@code true} if and only if this deque contains
   * at least one element {@code e} such that {@code o.equals(e)}.
   *
   * @param o object to be checked for containment in this deque
   * @return {@code true} if this deque contains the specified element
   */
  public boolean contains(Object o) {
    if (o == null) {
      return false;
    }
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      for (Node<E> p = first; p != null; p = p.next) {
        if (o.equals(p.item)) {
          return true;
        }
      }
      return false;
    } finally {
      lock.unlock();
    }
  }

    /*
     * TODO: Add support for more efficient bulk operations.
     *
     * We don't want to acquire the lock for every iteration, but we
     * also want other threads a chance to interact with the
     * collection, especially when count is close to capacity.
     */

//     /**
//      * Adds all of the elements in the specified collection to this
//      * queue.  Attempts to addAll of a queue to itself result in
//      * {@code IllegalArgumentException}. Further, the behavior of
//      * this operation is undefined if the specified collection is
//      * modified while the operation is in progress.
//      *
//      * @param c collection containing elements to be added to this queue
//      * @return {@code true} if this queue changed as a result of the call
//      * @throws ClassCastException            {@inheritDoc}
//      * @throws NullPointerException          {@inheritDoc}
//      * @throws IllegalArgumentException      {@inheritDoc}
//      * @throws IllegalStateException if this deque is full
//      * @see #add(Object)
//      */
//     public boolean addAll(Collection<? extends E> c) {
//         if (c == null)
//             throw new NullPointerException();
//         if (c == this)
//             throw new IllegalArgumentException();
//         final ReentrantLock lock = this.lock;
//         lock.lock();
//         try {
//             boolean modified = false;
//             for (E e : c)
//                 if (linkLast(e))
//                     modified = true;
//             return modified;
//         } finally {
//             lock.unlock();
//         }
//     }

  /**
   * Returns an array containing all of the elements in this deque, in
   * proper sequence (from first to last element).
   *
   * <p>The returned array will be "safe" in that no references to it are
   * maintained by this deque.  (In other words, this method must allocate
   * a new array).  The caller is thus free to modify the returned array.
   *
   * <p>This method acts as bridge between array-based and collection-based
   * APIs.
   *
   * @return an array containing all of the elements in this deque
   */
  @SuppressWarnings("unchecked")
  public Object[] toArray() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      Object[] a = new Object[count];
      int k = 0;
      for (Node<E> p = first; p != null; p = p.next) {
        a[k++] = p.item;
      }
      return a;
    } finally {
      lock.unlock();
    }
  }

  /**
   * Returns an array containing all of the elements in this deque, in
   * proper sequence; the runtime type of the returned array is that of
   * the specified array.  If the deque fits in the specified array, it
   * is returned therein.  Otherwise, a new array is allocated with the
   * runtime type of the specified array and the size of this deque.
   *
   * <p>If this deque fits in the specified array with room to spare
   * (i.e., the array has more elements than this deque), the element in
   * the array immediately following the end of the deque is set to
   * {@code null}.
   *
   * <p>Like the {@link #toArray()} method, this method acts as bridge between
   * array-based and collection-based APIs.  Further, this method allows
   * precise control over the runtime type of the output array, and may,
   * under certain circumstances, be used to save allocation costs.
   *
   * <p>Suppose {@code x} is a deque known to contain only strings.
   * The following code can be used to dump the deque into a newly
   * allocated array of {@code String}:
   *
   * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
   *
   * Note that {@code toArray(new Object[0])} is identical in function to
   * {@code toArray()}.
   *
   * @param a the array into which the elements of the deque are to be stored, if it is big enough;
   * otherwise, a new array of the same runtime type is allocated for this purpose
   * @return an array containing all of the elements in this deque
   * @throws ArrayStoreException if the runtime type of the specified array is not a supertype of
   * the runtime type of every element in this deque
   * @throws NullPointerException if the specified array is null
   */
  @SuppressWarnings("unchecked")
  public <T> T[] toArray(T[] a) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      if (a.length < count) {
        a = (T[]) java.lang.reflect.Array.newInstance
            (a.getClass().getComponentType(), count);
      }

      int k = 0;
      for (Node<E> p = first; p != null; p = p.next) {
        a[k++] = (T) p.item;
      }
      if (a.length > k) {
        a[k] = null;
      }
      return a;
    } finally {
      lock.unlock();
    }
  }

  public String toString() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      Node<E> p = first;
      if (p == null) {
        return "[]";
      }

      StringBuilder sb = new StringBuilder();
      sb.append('[');
      for (; ; ) {
        E e = p.item;
        sb.append(e == this ? "(this Collection)" : e);
        p = p.next;
        if (p == null) {
          return sb.append(']').toString();
        }
        sb.append(',').append(' ');
      }
    } finally {
      lock.unlock();
    }
  }

  /**
   * Atomically removes all of the elements from this deque.
   * The deque will be empty after this call returns.
   */
  public void clear() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      for (Node<E> f = first; f != null; ) {
        f.item = null;
        Node<E> n = f.next;
        f.prev = null;
        f.next = null;
        f = n;
      }
      first = last = null;
      count = 0;
      notFull.signalAll();
    } finally {
      lock.unlock();
    }
  }

  /**
   * Returns an iterator over the elements in this deque in proper sequence.
   * The elements will be returned in order from first (head) to last (tail).
   *
   * <p>The returned iterator is
   * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
   *
   * @return an iterator over the elements in this deque in proper sequence
   */
  public Iterator<E> iterator() {
    return new Itr();
  }

  /**
   * Returns an iterator over the elements in this deque in reverse
   * sequential order.  The elements will be returned in order from
   * last (tail) to first (head).
   *
   * <p>The returned iterator is
   * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
   *
   * @return an iterator over the elements in this deque in reverse order
   */
  public Iterator<E> descendingIterator() {
    return new DescendingItr();
  }

  /**
   * Base class for Iterators for LinkedBlockingDeque
   */
  private abstract class AbstractItr implements Iterator<E> {

    /**
     * The next node to return in next()
     */
    Node<E> next;

    /**
     * nextItem holds on to item fields because once we claim that
     * an element exists in hasNext(), we must return item read
     * under lock (in advance()) even if it was in the process of
     * being removed when hasNext() was called.
     */
    E nextItem;

    /**
     * Node returned by most recent call to next. Needed by remove.
     * Reset to null if this element is deleted by a call to remove.
     */
    private Node<E> lastRet;

    abstract Node<E> firstNode();

    abstract Node<E> nextNode(Node<E> n);

    AbstractItr() {
      // set to initial position
      final ReentrantLock lock = LinkedBlockingDeque.this.lock;
      lock.lock();
      try {
        next = firstNode();
        nextItem = (next == null) ? null : next.item;
      } finally {
        lock.unlock();
      }
    }

    /**
     * Returns the successor node of the given non-null, but
     * possibly previously deleted, node.
     */
    private Node<E> succ(Node<E> n) {
      // Chains of deleted nodes ending in null or self-links
      // are possible if multiple interior nodes are removed.
      for (; ; ) {
        Node<E> s = nextNode(n);
        if (s == null) {
          return null;
        } else if (s.item != null) {
          return s;
        } else if (s == n) {
          return firstNode();
        } else {
          n = s;
        }
      }
    }

    /**
     * Advances next.
     */
    void advance() {
      final ReentrantLock lock = LinkedBlockingDeque.this.lock;
      lock.lock();
      try {
        // assert next != null;
        next = succ(next);
        nextItem = (next == null) ? null : next.item;
      } finally {
        lock.unlock();
      }
    }

    public boolean hasNext() {
      return next != null;
    }

    public E next() {
      if (next == null) {
        throw new NoSuchElementException();
      }
      lastRet = next;
      E x = nextItem;
      advance();
      return x;
    }

    public void remove() {
      Node<E> n = lastRet;
      if (n == null) {
        throw new IllegalStateException();
      }
      lastRet = null;
      final ReentrantLock lock = LinkedBlockingDeque.this.lock;
      lock.lock();
      try {
        if (n.item != null) {
          unlink(n);
        }
      } finally {
        lock.unlock();
      }
    }
  }

  /**
   * Forward iterator
   */
  private class Itr extends AbstractItr {

    Node<E> firstNode() {
      return first;
    }

    Node<E> nextNode(Node<E> n) {
      return n.next;
    }
  }

  /**
   * Descending iterator
   */
  private class DescendingItr extends AbstractItr {

    Node<E> firstNode() {
      return last;
    }

    Node<E> nextNode(Node<E> n) {
      return n.prev;
    }
  }

  /**
   * A customized variant of Spliterators.IteratorSpliterator
   */
  static final class LBDSpliterator<E> implements Spliterator<E> {

    static final int MAX_BATCH = 1 << 25;  // max batch array size;
    final LinkedBlockingDeque<E> queue;
    Node<E> current;    // current node; null until initialized
    int batch;          // batch size for splits
    boolean exhausted;  // true when no more nodes
    long est;           // size estimate

    LBDSpliterator(LinkedBlockingDeque<E> queue) {
      this.queue = queue;
      this.est = queue.size();
    }

    public long estimateSize() {
      return est;
    }

    public Spliterator<E> trySplit() {
      Node<E> h;
      final LinkedBlockingDeque<E> q = this.queue;
      int b = batch;
      int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
      if (!exhausted &&
          ((h = current) != null || (h = q.first) != null) &&
          h.next != null) {
        Object[] a = new Object[n];
        final ReentrantLock lock = q.lock;
        int i = 0;
        Node<E> p = current;
        lock.lock();
        try {
          if (p != null || (p = q.first) != null) {
            do {
              if ((a[i] = p.item) != null) {
                ++i;
              }
            } while ((p = p.next) != null && i < n);
          }
        } finally {
          lock.unlock();
        }
        if ((current = p) == null) {
          est = 0L;
          exhausted = true;
        } else if ((est -= i) < 0L) {
          est = 0L;
        }
        if (i > 0) {
          batch = i;
          return Spliterators.spliterator
              (a, 0, i, Spliterator.ORDERED | Spliterator.NONNULL |
                  Spliterator.CONCURRENT);
        }
      }
      return null;
    }

    public void forEachRemaining(Consumer<? super E> action) {
      if (action == null) {
        throw new NullPointerException();
      }
      final LinkedBlockingDeque<E> q = this.queue;
      final ReentrantLock lock = q.lock;
      if (!exhausted) {
        exhausted = true;
        Node<E> p = current;
        do {
          E e = null;
          lock.lock();
          try {
            if (p == null) {
              p = q.first;
            }
            while (p != null) {
              e = p.item;
              p = p.next;
              if (e != null) {
                break;
              }
            }
          } finally {
            lock.unlock();
          }
          if (e != null) {
            action.accept(e);
          }
        } while (p != null);
      }
    }

    public boolean tryAdvance(Consumer<? super E> action) {
      if (action == null) {
        throw new NullPointerException();
      }
      final LinkedBlockingDeque<E> q = this.queue;
      final ReentrantLock lock = q.lock;
      if (!exhausted) {
        E e = null;
        lock.lock();
        try {
          if (current == null) {
            current = q.first;
          }
          while (current != null) {
            e = current.item;
            current = current.next;
            if (e != null) {
              break;
            }
          }
        } finally {
          lock.unlock();
        }
        if (current == null) {
          exhausted = true;
        }
        if (e != null) {
          action.accept(e);
          return true;
        }
      }
      return false;
    }

    public int characteristics() {
      return Spliterator.ORDERED | Spliterator.NONNULL |
          Spliterator.CONCURRENT;
    }
  }

  /**
   * Returns a {@link Spliterator} over the elements in this deque.
   *
   * <p>The returned spliterator is
   * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
   *
   * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT},
   * {@link Spliterator#ORDERED}, and {@link Spliterator#NONNULL}.
   *
   * @return a {@code Spliterator} over the elements in this deque
   * @implNote The {@code Spliterator} implements {@code trySplit} to permit limited parallelism.
   * @since 1.8
   */
  public Spliterator<E> spliterator() {
    return new LBDSpliterator<E>(this);
  }

  /**
   * Saves this deque to a stream (that is, serializes it).
   *
   * @param s the stream
   * @throws java.io.IOException if an I/O error occurs
   * @serialData The capacity (int), followed by elements (each an {@code Object}) in the proper
   * order, followed by a null
   */
  private void writeObject(java.io.ObjectOutputStream s)
      throws java.io.IOException {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
      // Write out capacity and any hidden stuff
      s.defaultWriteObject();
      // Write out all elements in the proper order.
      for (Node<E> p = first; p != null; p = p.next) {
        s.writeObject(p.item);
      }
      // Use trailing null as sentinel
      s.writeObject(null);
    } finally {
      lock.unlock();
    }
  }

  /**
   * Reconstitutes this deque from a stream (that is, deserializes it).
   *
   * @param s the stream
   * @throws ClassNotFoundException if the class of a serialized object could not be found
   * @throws java.io.IOException if an I/O error occurs
   */
  private void readObject(java.io.ObjectInputStream s)
      throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();
    count = 0;
    first = null;
    last = null;
    // Read in all elements and place in queue
    for (; ; ) {
      @SuppressWarnings("unchecked")
      E item = (E) s.readObject();
      if (item == null) {
        break;
      }
      add(item);
    }
  }

}
